{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Une IA pour le Morpion (Algorithme MinMax)\n", "\n", "L'algorithme MinMax est un algorithme qui permet à un ordinateur de jouer à un jeu à somme nulle (c'est-à-dire où le gain d'un joueur entraîne la perte de l'autre) et à information complète (l'intégralité du jeu est connu par les deux joueurs) comme le morpion, les échecs, etc.\n", "\n", "On peut voir un jeu comme le morpion sous la forme d'un arbre : chaque sommet représente une position du jeu, et les arêtes représentent les coups possibles à jouer.\n", "\n", "Le principe est alors de parcourir cet arbre, en attribuant un score à chacune des positions.\n", "Ce score représente l'issue de la partie si l'adversaire joue parfaitement bien.\n", "\n", "Par exemple, au morpion, si une position a un score de 1, cela signifie que c'est le joueur 1 qui va gagner, s'il joue parfaitement bien, bien sûr." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Représentation du Jeu\n", "\n", "On attribue des numéros aux joueurs, le joueur qui commence est le joueur `1`, et l'autre, le joueur `-1`.\n", "\n", "Le plateau est représenté par un tuple de la forme `((0, 0, 1), (0, -1, 1), (1, -1, 0))` par exemple, où chaque élément du tuple représente l'état de la case qui correspond.\n", "\n", "Voilà quelques fonctions qui représentent le morpion.\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "import numpy as np\n", "import matplotlib.pyplot as plt\n", "from matplotlib.collections import LineCollection\n", "\n", "def morpion_initial(dim=3):\n", " \"\"\" \n", " Crée un jeu de morpion vide de taille dim x dim.\n", " \"\"\"\n", " return tuple(tuple(0 for i in range(dim)) for j in range(dim))\n", "\n", "def gagnant(position, joueur):\n", " \"\"\" \n", " Renvoie True si le joueur gagne et False sinon\n", " \"\"\"\n", " dim = len(position)\n", " a = np.array(position)\n", " \n", " return np.any(np.sum(a == joueur, axis=0) == dim) \\\n", " or np.any((np.sum(a == joueur, axis=1) == dim)) \\\n", " or np.sum(np.diag(a == joueur)) == dim \\\n", " or np.sum(np.diag(np.fliplr(a == joueur))) == dim\n", "\n", "def score(position):\n", " \"\"\" \n", " Renvoie le score d'une position : 1 si le joueur 1 gagne, et -1 si le joueur -1 gagne.\n", " Si personne ne gagne, la fonction renvoie 0 (que la partie soit finie ou non.)\n", " \"\"\"\n", " return -1 * gagnant(position, -1) + 1 * gagnant(position, 1)\n", " \n", "def coups_possibles(position, joueur):\n", " \"\"\"\n", " Renvoie l'ensemble des positions qu'un joueur peut atteindre dans une position donnée.\n", " \"\"\"\n", " coups = []\n", " \n", " for x in range(len(position)):\n", " for y in range(len(position)):\n", " if position[x][y] == 0:\n", " coups.append(jouer(position, x, y, joueur))\n", "\n", " return coups\n", "\n", "def jouer(position, x, y, joueur):\n", " \"\"\"\n", " Renvoie la position obtenue après que le joueur `joueur` a joué en (x, y).\n", " \"\"\"\n", " return tuple(position[i] if i != x else position[i][:y] + (joueur,) + position[i][y+1:] \\\n", " for i in range(len(position)))\n", "\n", "def afficher_morpion(position):\n", " \"\"\"\n", " Affiche la position.\n", " \"\"\"\n", " dim = len(position)\n", " position = np.array(position)\n", " joueur1 = np.where(position == 1)\n", " joueur2 = np.where(position == -1)\n", " \n", " lines = [((i, 0), (i, dim)) for i in range(dim + 1)] \\\n", " + [((0, i), (dim, i)) for i in range(dim + 1)]\n", " \n", " fig, ax = plt.subplots()\n", " ax.add_collection(LineCollection(lines, colors=\"black\"))\n", " ax.set_xlim(-0.01, dim+0.01)\n", " ax.set_ylim(-0.01, dim+.01)\n", " ax.set_aspect(1)\n", " ax.axis(\"off\")\n", " \n", " for x, y in zip(joueur1[0], joueur1[1]):\n", " ax.plot((x+0.1,x+0.9), (y+0.1,y+0.9), color=\"black\", lw=2)\n", " ax.plot((x+0.9,x+0.1), (y+0.1,y+0.9), color=\"black\", lw=2)\n", " \n", " for x, y in zip(joueur2[0], joueur2[1]):\n", " cc = plt.Circle((x + 0.5, y + 0.5), 0.45, fill=False, color=\"#f70077\", lw=2)\n", " ax.add_artist(cc)" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "pos = ((1, 0),(0, 1))\n", "score(pos)\n", "afficher_morpion(pos)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Par exemple, voilà une position où le joueur 1 a gagné :" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "position = ((1, -1, -1), (0, 1, 0), (1, -1, 1))\n", "afficher_morpion(position)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** En utilisant la fonction `coups_possibles`, afficher l'ensemble des positions que l'on peut obtenir en partant de la position représentée par le tuple `((1, 0, 0), (0, -1, 0), (1, 0, 0))`, sachant que c'est ici au joueur `-1` (avec les ronds) de joueur." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Arbre du Jeu\n", "\n", "Comme dit au dessus, l'arbre du jeu de morpion est un arbre dont la racine est la position initiale du jeu.\n", "Pour des raisons de place en mémoire et de difficulté de la représentation, on va se contenter de représenter l'arbre du jeu de morpion de taille 2x2.\n", "\n", "La fonction `arbre_morpion` calcule cet arbre." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": false }, "outputs": [], "source": [ "import networkx as nx\n", "from hierarchy import hierarchy_pos\n", "\n", "\n", "def arbre_morpion(dimension):\n", " sommets = [(0, morpion_initial(dimension), 1)]\n", " aretes = []\n", " i = 0\n", " \n", " a_parcourir = sommets.copy()\n", " \n", " while a_parcourir:\n", " sommet = a_parcourir.pop()\n", " _, position, joueur = sommet\n", " \n", " sommets.append(sommet)\n", " if score(position) == 0: \n", " for position in coups_possibles(position, joueur):\n", " i += 1\n", " nouveau_sommet = (i, position, -joueur)\n", "\n", " a_parcourir.append(nouveau_sommet)\n", " aretes.append((sommet, nouveau_sommet))\n", " \n", " G = nx.DiGraph()\n", " G.add_nodes_from(sommets)\n", " G.add_edges_from(aretes)\n", " \n", " return G" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Quesiton.** Commenter le fonctionnement de cet algorithme. Quelle différence observez-vous avec les algorithmes classiques de parcours en largeur dans un graphe ?\n", "\n", "Remarquez bien ici que certains sommets représentent la même position, mais on considère qu'ils sont différents car le chemin parcouru pour les obtenir est différent (si les coups sont joués dans un ordre différents, on peut obtenir la même position mais avoir joué des coups différents)." ] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": false }, "outputs": [], "source": [ "# calcul de l'arbre\n", "G_morpion = arbre_morpion(2)\n", "\n", "# affichage de l'arbre\n", "fig, ax = plt.subplots(figsize=(25,10))\n", "\n", "# position des sommets de l'arbre\n", "pos = hierarchy_pos(G_morpion, (0, ((0,0),(0,0)), 1))\n", "\n", "# couleurs des noeuds\n", "couleurs_map = [\"pink\" if s[2] == 1 else \"turquoise\" for s in G_morpion.nodes()]\n", "\n", "# calcul des labels\n", "d = {1: \"X\", -1: \"O\", 0: \"_\"}\n", "labels= {s: \"\\n\".join(map(lambda l: \" \".join(map(lambda x: d[x],l)),s[1])) for s in G_morpion.nodes()}\n", "\n", "# affichage\n", "nx.draw(G_morpion, pos, edgecolors=\"black\", node_color=couleurs_map, \n", " labels=labels, with_labels=True, node_size=1200, node_shape=\"s\")" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Chaque sommet représente une position, et on passe d'une position à une autre en jouant un coup.\n", "Les sommets représentés en rose sont les sommets où c'est au tour du joueur 1, et ceux en turquoise ceux où c'est le tour du joueur -1.\n", "\n", "Vous remarquez bien que chacun des niveaux de profondeur dans le graphe représente le tour d'un joueur.\n", "\n", "On remarque également qu'un chemin dans l'arbre s'arrête quand un des deux joueurs a gagné." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** À partir de l'arbre ci-dessus, commentez les issues possibles d'une partie sur une grille de taille 2x2. Est-ce qu'une partie de ce jeu vous semble intéressante ?" ] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Remarque.** On s'est ici limités à un arbre pour le morpion de taille $2 \\times 2$, car ici l'arbre a déjà $41$ sommets.\n", "\n", "En taille $3 \\times 3$, l'arbre du jeu est beaucoup plus grand car il a de l'ordre de $100000$ sommets.\n", "Il est donc environ $2500$ fois plus grand, ce qui s'explique par deux choses : l'arbre est plus profond, et il y a plus de branchements à chaque niveau." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Algorithme MinMax\n", "\n", "### Évaluation d'une Position\n", "\n", "Comme dans la plupart des IA qui jouent à des jeux, l'élément le plus important consiste à évaluer \"qui gagne\" dans une position donnée.\n", "\n", "Intuitivement, c'est ce que l'on fait quand on joue : on imagine les coups que l'on va jouer, puis on regarde si on a une chance de gagner après ce coup là.\n", "Après avoir passé en revue tous les coups possibles, on peut faire un choix éclairé.\n", "\n", "Et bien la machine fait de même : elle évalue la position pour savoir qui gagne, perd, ou si c'est match nul, puis elle prend une décision basé là dessus.\n", "\n", "### Principe de l'Algorithme MinMax\n", "\n", "L'algorithme MinMax est un algorithme d'évaluation de position.\n", "\n", "Le principe est simple : on part des feuilles de l'arbre, pour lesquelles l'évaluation est facile, soit un joueur a gagné, et on attribue à la feuille le score de `1` ou `-1`, soit c'est un match nul, et le score est alors `0`.\n", "\n", "Puis on remonte dans l'arbre, et pour un sommet interne de l'arbre, il y a deux possibilités :\n", "\n", "* soit c'est au joueur 1 de jouer, et le score que l'on attribue au sommet est le **maximum** des scores de ses sommets enfants ;\n", "\n", "* soit c'est au joueur -1 de jouer, et le score que l'on attribue au sommet est le **minimum** des scores de ses sommets enfants.\n", "\n", "Intuitivement, cela correspond à répondre à la question \"si je joue le meilleur coup, et que mon adversaire joue les meilleurs coups, quelle est l'issue de la partie ?\"\n", "\n", "On peut donc définir un algorithme récursif de score, que l'on appellera `minmax` :\n", "* si la partie est terminée, on associe le score qui correspond à la position (1 si le joueur 1 gagne, -1 si le joueur -1 gagne, et 0 sinon) ;\n", "* sinon, si c'est au joueur 1 de jouer, `minmax(sommet) = max([minmax(sommet_enfant) pour chaque sommet enfant])` ;\n", "* sinon, si c'est au joueur -1 de jouer, `minmax(sommet) = min([minmax(sommet_enfant) pour chaque sommet enfant])`.\n", "\n", "### Mais si l'arbre est trop grand ?\n", "\n", "On vient de voir que stocker tout l'arbre en mémoire semble compliqué, car il y a beaucoup de sommets... mais comment faire alors pour quand même trouver une solution à ce jeu, qui semble, de plus, plutôt simple ?\n", "\n", "En fait, et c'est là une idée cruciale, on peut explorer l'arbre **sans garder tout l'arbre en mémoire**.\n", "Vous remarquerez en effet facilement que, pour passer d'un sommet à un autre, il suffit de connaître la position et de connaître les règles pour pouvoir calculer les coups que l'on a le droit de jouer.\n", "Et explorer $100000$ sommets, même si c'est beaucoup, c'est encore envisageable.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Implémenter l'algorithme MinMax décrit ci-dessus. On définira une fonction récursive `minmax` qui prend en argument une position et le joueur dont c'est le tour, et qui renvoie le score associé à la position en utilisant l'algorithme MinMax décrit ci-dessus (et dans le cours)." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def minmax(position, joueur):\n", " # implémentez l'algorithme ici" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Calculez le score du jeu de morpion en taille $3 \\times 3$ à partir de la position initiale. Que dire alors du jeu de morpion ?" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": false }, "outputs": [], "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Élagage AlphaBeta\n", "\n", "Comme vous pouvez le constater, évaluer une position prend quand même du temps.\n", "\n", "En fait, on n'a pas besoin d'explorer l'arbre jusqu'au bout à chaque fois : parfois, on sait qu'un coup ne vaut pas le coup car on a déjà exploré un meilleur coup pour l'adversaire, et on peut donc l'ignorer.\n", "C'est le principe de l'**élagage alpha-beta**." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** Référez vous au cours pour implémenter la fonction `alpha_beta`, qui exécute l'algorithme MinMax avec l'élagage AlphaBeta." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def alpha_beta(position, joueur, alpha=-np.inf, beta=np.inf):\n", " # implémentez l'algorithme ici" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Faisons jouer la machine !" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Question.** En utilisant la fonction `alpha_beta`, définir une fonction qui fait jouer deux ordinateurs l'un contre l'autre, en affichant les coups joués." ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "def autoplay(dimension):\n", " # implémentez la fonction ici" ] }, { "cell_type": "code", "execution_count": null, "metadata": { "scrolled": false }, "outputs": [], "source": [ "autoplay(3)" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.5" } }, "nbformat": 4, "nbformat_minor": 4 }